1. Field of the Invention
This invention relates to optimization of computer code to achieve faster execution. More particularly, this invention relates to gathering of data about the frequencies with which different execution paths in a program are traversed.
2. Description of the Related Art
Profiling as a tool for optimization and restructuring is well known in the computer arts. Profile-based optimizations are widely used today in commercial compilers and post-link optimization tools. For example, post-link run time profiling is described by Henis et al., in “Feedback Based Post-Link Optimization for Large Subsystems,” Second Workshop on Feedback Directed Optimization (Haifa, Israel, November, 1999), pages 13 20; and by Schmidt et al., in “Profile-Directed Restructuring of Operating System Code,” IBM Systems Journal 37:2 (1998), pages 270 297.
Runtime profiling of a program creates a log recording usage statistics of each code block in two stages. First, in an instrumentation stage, each basic block or function is modified with either a new header or footer, wherein the added code increments a counter every time that basic block or function is run. In the second stage (the execution stage), the modified program is executed. At the end of the execution, the counters are written into a log file. Statistical analysis of the frequency of use of each basic block provides a method to rank the code blocks by importance. Code blocks that are frequently executed are called “hot” blocks, as opposed to rarely executed “cold” blocks.
Two general methods of obtaining profiling information are known, for example, from U.S. Pat. No. 7,120,906 to Stephenson et al. Sampling is the periodic measurement of a computer's register contents during execution of the program binary. The approach identifies where most of the time is spent during execution of a particular computer program. However, it is difficult to derive information about the source code or any of the series of intermediate representations that are produced during the compilation process.
A second method, known as instrumentation, is the insertion of extra instructions into the code during compilation in order to collect information at run time. There are disadvantages of such an invasive approach, e.g., increased code, prolonged execution time, and possibly altered program behavior. On the other hand, instrumentation is amenable to source code and intermediate representations of a program. Indeed, it is even proposed to dynamically add instrumentation code to a program while the target program is executing, as described in U.S. Pat. No. 7,165,242 to Dmitriev.